using System;

namespace G2Tech.SharedContext
{
    /// <summary>
    /// Spanning Tree Engine
    /// </summary>
    /// <see cref="http://it.wikipedia.org/wiki/Algoritmo_di_Prim"/>
    public class SpanningTreeEngine
    {
        #region Constructor
        
        /// <summary>
        /// Constructor
        /// </summary>
        public SpanningTreeEngine()
        {
            Nodes = new System.Collections.ArrayList();
            AvailableLinks = new System.Collections.ArrayList();
            SelectedLinks = new System.Collections.ArrayList();           
        } 

        #endregion

        #region Properties
        
        /// <summary>
        /// Gets the list of all the known Nodes. IT WILL CONTAINS A LIST OF DeviceAddress entities.
        /// </summary>
        public System.Collections.ArrayList Nodes { get; internal set; }
        
        /// <summary>
        /// Gets the list of all the known Link including their costs. IT WILL CONTAINST A LIST OF SpanningTreeLinkCost entities.
        /// </summary>
        public System.Collections.ArrayList AvailableLinks { get; internal set; }

        /// <summary>
        /// Gets the list of the currently selected links IT WILL CONTAINST A LIST OF SpanningTreeLinkCost entities.
        /// </summary>
        public System.Collections.ArrayList SelectedLinks { get; internal set; }

        #endregion


        #region Members
        
        /// <summary>
        /// node to be yet evaluated by the spanning tree algorithm
        /// </summary>
        private System.Collections.ArrayList _nodeToEvaluate = new System.Collections.ArrayList();

        /// <summary>
        /// node that is already evaluated by the spanning tree algorithm
        /// </summary>
        private System.Collections.ArrayList _nodeEvaluated = new System.Collections.ArrayList();

        #endregion

        /// <summary>
        /// Create the Spanning Tree
        /// </summary>
        public void CreateTree(System.Collections.ArrayList availableLinks)
        {
            if (AvailableLinks == null)
            {
                AvailableLinks = new System.Collections.ArrayList();
            }
            else
            {
                AvailableLinks.Clear();
            }

            //reset the selected links
            if (SelectedLinks == null)
            {
                SelectedLinks = new System.Collections.ArrayList();
            }
            else
            {
                SelectedLinks.Clear();
            }

            if (Nodes == null)
            {
                Nodes = new System.Collections.ArrayList();
            }
            else
            {
                Nodes.Clear();
            }

            if (_nodeToEvaluate == null)
            {
                _nodeToEvaluate = new System.Collections.ArrayList();
            }
            else
            {
                _nodeToEvaluate.Clear();
            }
        
            //start the algorithms...
            foreach (var linkObj in availableLinks)
            {
                var link = linkObj as SpanningTreeLinkCost;

                AvailableLinks.Add(link);

                bool canAddNode = true;

                foreach (var nodeObk in Nodes)
                { 
                    var node = nodeObk as DeviceAddress;
                    if (node.Address.Equals(link.NodeA.Address))
                    {
                        canAddNode = false;
                        break;
                    }
                }

                if (canAddNode)
                {
                    Nodes.Add(link.NodeA);
                    _nodeToEvaluate.Add(link.NodeA);
                }

                canAddNode = true;

                foreach (var nodeObk in Nodes)
                {
                    var node = nodeObk as DeviceAddress;
                    if (node.Address.Equals(link.NodeB.Address))
                    {
                        canAddNode = false;
                        break;
                    }
                }

                if (canAddNode)
                {
                    Nodes.Add(link.NodeB);
                    _nodeToEvaluate.Add(link.NodeB);
                }
            }

            if (_nodeToEvaluate.Count > 0)
            {
                //select the first node as "seed"
                int seedIndex = 0;

                _nodeEvaluated.Add(_nodeToEvaluate[seedIndex]);
                _nodeToEvaluate.RemoveAt(seedIndex);

                //it will contains all the temporary links for a round...
                var temporaryWorkingLinks = new System.Collections.ArrayList();

                //now loop until all the nodes are evaluated!
                while (_nodeToEvaluate.Count > 0)
                {
                    foreach (var node in _nodeEvaluated)
                    {
                        var linksOfThisNode = findNewLinkOfNode(node as DeviceAddress);
                        temporaryWorkingLinks = mergeLinks(linksOfThisNode, temporaryWorkingLinks);
                    }

                    if (temporaryWorkingLinks.Count == 0)
                    {
                        throw new SpanningTreeException("Impossible build the Spanning Tree, Tree is isolated");
                    }

                    var economicLink = findLowCostLink(temporaryWorkingLinks); //now i've to find the most economic link!
                    SelectedLinks.Add(economicLink); //add to the selected link!!!!!! GOOD!

                    temporaryWorkingLinks.Clear();

                    //and now add the new node into the evaluated nodes and remove from the node to evaluate list!
                    DeviceAddress newEvaluatedNode = findTheNewNodeFromNewLink(economicLink);

                    _nodeToEvaluate.Remove(newEvaluatedNode);
                    _nodeEvaluated.Add(newEvaluatedNode);
                }
            }
        }

        private DeviceAddress findTheNewNodeFromNewLink(SpanningTreeLinkCost newLink)
        {
            bool foundNewNode = true;

            foreach (var nodeObj in _nodeEvaluated)
            { 
                var node = nodeObj as DeviceAddress;

                if (newLink.NodeA.Address.Equals(node.Address))
                {
                    foundNewNode = false;
                    break;
                }
            }

            if (foundNewNode)
            {
                return newLink.NodeA;
            }

            foundNewNode = true;

            foreach (var nodeObj in _nodeEvaluated)
            {
                var node = nodeObj as DeviceAddress;

                if (newLink.NodeB.Address.Equals(node.Address))
                {
                    foundNewNode = false;
                    break;
                }
            }

            if (foundNewNode)
            {
                return newLink.NodeB;
            }


            return null;
        }

        /// <summary>
        /// find the most economic link
        /// </summary>
        /// <param name="links"></param>
        /// <returns></returns>
        private SpanningTreeLinkCost findLowCostLink(System.Collections.ArrayList links)
        {
            SpanningTreeLinkCost selectedLink = links[0] as SpanningTreeLinkCost;

            foreach (var linkObj in links)
            { 
                var link = linkObj as SpanningTreeLinkCost;

                if (link.Cost < selectedLink.Cost)
                {
                    selectedLink = link;
                }
            }

            return selectedLink;
        }

        /// <summary>
        /// merge two list of links 
        /// </summary>
        /// <param name="temporaryWorkingLinks"></param>
        /// <param name="linksOfThisNode"></param>
        /// <returns></returns>
        private System.Collections.ArrayList mergeLinks(System.Collections.ArrayList linkListA, System.Collections.ArrayList linkListB)
        {
            var mergedLinkList = new System.Collections.ArrayList();

            foreach (var linkAObj in linkListA)
            {
                var linkA = linkAObj as SpanningTreeLinkCost;

                bool canAdd = true;

                foreach (var linkBObj in linkListB)
                {
                    var linkB = linkBObj as SpanningTreeLinkCost;
                    
                    if( (linkA.NodeA == linkB.NodeA) && (linkA.NodeB == linkB.NodeB))
                    {
                        canAdd = false;
                        break;
                    }
                }

                if (canAdd)
                {
                    mergedLinkList.Add(linkA);
                }
            }

            //now merge the remaining link from B!
            foreach (var linkBObj in linkListB)
            {
                var linkB = linkBObj as SpanningTreeLinkCost;

                bool canAdd = true;

                foreach (var linkMergedObj in mergedLinkList)
                {
                    var linkMerged = linkMergedObj as SpanningTreeLinkCost;

                    if ((linkMerged.NodeA == linkB.NodeA) && (linkMerged.NodeB == linkB.NodeB))
                    {
                        canAdd = false;
                        break;
                    }
                }
                
                if (canAdd)
                {
                    mergedLinkList.Add(linkB);
                }
            }

            return mergedLinkList;
        }

        /// <summary>
        /// find all the link for a node skipping the links that are currently already selected
        /// and links that brings to nodes already reached.
        /// </summary>
        /// <param name="deviceAddress"></param>
        /// <returns></returns>
        private System.Collections.ArrayList findNewLinkOfNode(DeviceAddress deviceAddress)
        {
            var links = new System.Collections.ArrayList();

            foreach (var linkObj in this.AvailableLinks)
            {
                var link = linkObj as SpanningTreeLinkCost;

                if (link.NodeA.Address.Equals(deviceAddress.Address) || link.NodeB.Address.Equals(deviceAddress.Address))
                {
                    bool canAddThisLink = true;

                    //check if this link contains a node that is already sleected!
                    DeviceAddress nodeToCheckIfAlreadyUsed = null;

                    if (link.NodeA.Address.Equals(deviceAddress.Address))
                        nodeToCheckIfAlreadyUsed = link.NodeB;

                    if (link.NodeB.Address.Equals(deviceAddress.Address))
                        nodeToCheckIfAlreadyUsed = link.NodeA;

                    //look if that node is already reached!
                    foreach (var nodeObj in _nodeEvaluated)
                    {
                        var node = nodeObj as DeviceAddress;
                        if (node.Address.Equals(nodeToCheckIfAlreadyUsed.Address))
                        {
                            canAddThisLink = false;
                            break;
                        }
                    }

                    if (!canAddThisLink)
                    {
                        continue;
                    }

                    //check if this link is already in use!
                    foreach (var selectedLinkObj in this.SelectedLinks)
                    {
                        var selectedLink = selectedLinkObj as SpanningTreeLinkCost;

                        if ((link.NodeA == selectedLink.NodeA) && (link.NodeB == selectedLink.NodeB))
                        {
                            canAddThisLink = false;
                            break;
                        }
                    }

                    if (canAddThisLink)
                    {
                        links.Add(linkObj);
                    }
                }
            }

            return links;
        }


    }
}
